ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group01b.txt/000047_icon-group-sender_Tue Mar 6 12:31:52 2001.msg

Internet Message Format | 2002-01-03 | 4KB

Return-Path: <icon-group-sender>
Received: (from root@localhost)
    by baskerville.CS.Arizona.EDU (8.11.1/8.11.1) id f26JUmA14033
    for icon-group-addresses; Tue, 6 Mar 2001 12:30:48 -0700 (MST)
Message-Id: <[e-mail]>
Date: Tue, 06 Mar 2001 10:42:10 -0500
From: "Steve Graham" <[e-mail]>
To: <[e-mail]>, <[e-mail]>
Subject: Re: New Scientist puzzle
Content-Disposition: inline
X-MIME-Autoconverted: from quoted-printable to 8bit by baskerville.CS.Arizona.EDU id f26Fi7804551
Errors-To: [e-mail]
Status: RO
Content-Length: 2852

Cary,

   This puzzle seems to have taken on a life of its own, especially in the comp.lang.apl forum.  Over 30 posts.

   Thanks for both of your submissions.


Steve


>>> Cary Coutant <[e-mail]> 03/05/01 08:20PM >>>
After doing a solution in Icon, I got to thinking that this problem would
be fun to solve in APL. After dusting off my APL programming skills
(dormant for 26 years now), I wasn't able to come up with something as
elegant as I had hoped for. (Some may question the use of "elegant" in
the same sentence as "APL.")

My apologies for going so far off topic, but we've already seen a
solution in MUMPS (another language I haven't seen for 26 years), and I
thought this would be another interesting contrast to Icon.

What I wanted to do was something like this (with accomodation for the
ASCII character set):

Start with a function F that compares two numbers X and Y and returns a
boolean indicating whether they match the pattern. The trick in line [2]
is exactly the same trick I used with map() in my Icon solution.

      del R <- X F Y; NUMS
[1]   NUMS <- (((rho PAT1), 0) format X), ((rho PAT2), 0) format Y
[2]   R <- and / (PATS[NUMS iota NUMS]=PATS), NUMS[PATS iota PATS]=NUMS
      del

The function VIER takes a vector of squares (line [4]), and forms the
outer result (line [5]) of that vector with itself, using my function F.
This would produce a matrix of booleans indicating each pair of squares
that satisfies the pattern (the first condition). In line [6], I
plus-reduce the matrix row-wise and column-wise, check for rows and
columns that have only one solution, expand those reduced vectors out
again, then and everything together to form a matrix with only a single
1. Lines 7 and 8 print the two squares corresponding to that entry.

      del VIER; SQ; M
[1]   PAT1 <- 'VIER'
[2]   PAT2 <- 'NEUN'
[3]   PATS <- PAT1,PAT2
[4]   SQ <- (31 drop iota 99) * 2
[5]   M <- SQ jot . F SQ
[6]   M <- M & ((rho M) rho 1 = + bar/ M) &
               transpose (reverse rho M) rho 1 = +/M
[7]   (or / M) / SQ
[8]   (or bar/ M) / SQ
      del

Unfortunately, APL doesn't support outer result with user-defined
functions. (To me, that's like not supporting user-defined generators in
Icon!) I ended up writing a function XMATCH that produced the outer
result using traditional looping techniques.

Then I had one more problem. The version of APL I was using (CAPLIB for
DOS, running on a Mac under Virtual PC) crashed when I tried to make the
68-by-68 result matrix. I ended up having to filter the list of squares
into two lists: VSQ containing only those squares that matched the
pattern "VIER", and NSQ containing only those squares that matched the
pattern "NEUN". With the smaller matrix to deal with, it was able to come
up with the solution.

It was a fun exercise, though!

-cary